/**
 * 项目名称: Topic_41.cpp
 * 项目路径: study/DataStructure/刷题/一轮/第五天 数组+散列表
 * 编辑时间: 2024年09月06日09时28分38秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    const int N = 200003;
    int h[200003];

    int find(int x) {
        int k = (x % N + N) % N;
        while (h[k] != 0x3f3f3f3f && h[k] != x) {
            k++;
            if (k == N)k = 0;
        }
        return k;
    }

    void init() {
        for (int i = 0; i < N; i++)h[i] = 0x3f3f3f3f;
    }

    int firstMissingPositive(vector<int> &nums) {
        init();
        for (auto x: nums)h[find(x)] = x;
        int ans = 1;
        for (int i = 1; i < 0x3f3f3f3f; i++)
            if (h[find(i)] == 0x3f3f3f3f) {
                ans = i;
                break;
            }
        return ans;
    }
};
